<!DOCTYPE html>
<html lang="zh-CN">

<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="robots" content="noodp" />
    <title class="pjax-title">Skiplist - </title><meta name="Description" content=""><meta property="og:title" content="Skiplist" />
<meta property="og:description" content="学习跳表的总结以及核心的代码实现" />
<meta property="og:type" content="article" />
<meta property="og:url" content="http://gzhcoming.gitee.io/posts/%E8%B7%B3%E8%A1%A8skiplist/" /><meta property="og:image" content="https://s2.loli.net/2022/03/12/wQSVOeChsH3INYL.png" /><meta property="article:section" content="posts" />
<meta property="article:published_time" content="2022-03-12T11:41:08+08:00" />
<meta property="article:modified_time" content="2022-03-12T11:41:08+08:00" />


<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://s2.loli.net/2022/03/12/wQSVOeChsH3INYL.png"/>

<meta name="twitter:title" content="Skiplist"/>
<meta name="twitter:description" content="学习跳表的总结以及核心的代码实现"/>
<meta name="application-name" content="">
<meta name="apple-mobile-web-app-title" content="">

<meta name="theme-color" content="#f8f8f8"><link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" />
        <link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
        <link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png"><link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png"><link rel="canonical" href="http://gzhcoming.gitee.io/posts/%E8%B7%B3%E8%A1%A8skiplist/" /><link rel="prev" href="http://gzhcoming.gitee.io/posts/081-utilities/" /><link rel="next" href="http://gzhcoming.gitee.io/posts/git/" /><link rel="stylesheet" href="/lib/normalize/normalize.min.css"><link rel="stylesheet" href="/css/style.min.css"><link rel="preload" as="style" onload="this.onload=null;this.rel='stylesheet'" href="/lib/fontawesome-free/all.min.css">
        <noscript><link rel="stylesheet" href="/lib/fontawesome-free/all.min.css"></noscript><link rel="preload" as="style" onload="this.onload=null;this.rel='stylesheet'" href="/lib/animate/animate.min.css">
        <noscript><link rel="stylesheet" href="/lib/animate/animate.min.css"></noscript><script type="application/ld+json">
    {
        "@context": "http://schema.org",
        "@type": "BlogPosting",
        "headline": "Skiplist",
        "inLanguage": "zh-CN",
        "mainEntityOfPage": {
            "@type": "WebPage",
            "@id": "http:\/\/gzhcoming.gitee.io\/posts\/%E8%B7%B3%E8%A1%A8skiplist\/"
        },"genre": "posts","keywords": "data struct","wordcount":  1918 ,
        "url": "http:\/\/gzhcoming.gitee.io\/posts\/%E8%B7%B3%E8%A1%A8skiplist\/","datePublished": "2022-03-12T11:41:08+08:00","dateModified": "2022-03-12T11:41:08+08:00","publisher": {
            "@type": "Organization",
            "name": "作者"},"author": {
                "@type": "Person",
                "name": "作者"
            },"description": ""
    }
    </script></head>

<body header-desktop="" header-mobile=""><script type="text/javascript">
        function setTheme(theme) {document.body.setAttribute('theme', theme);}
        function saveTheme(theme) {window.localStorage && localStorage.setItem('theme', theme);}
        function getMeta(metaName) {const metas = document.getElementsByTagName('meta'); for (let i = 0; i < metas.length; i++) if (metas[i].getAttribute('name') === metaName) return metas[i]; return '';}
        if (window.localStorage && localStorage.getItem('theme')) {let theme = localStorage.getItem('theme');theme === 'light' || theme === 'dark' || theme === 'black' ? setTheme(theme) : (window.matchMedia && window.matchMedia('(prefers-color-scheme: dark)').matches ? setTheme('dark') : setTheme('light')); } else { if ('' === 'light' || '' === 'dark' || '' === 'black') setTheme(''), saveTheme(''); else saveTheme('auto'), window.matchMedia && window.matchMedia('(prefers-color-scheme: dark)').matches ? setTheme('dark') : setTheme('light');}
        let metaColors = {'light': '#f8f8f8','dark': '#252627','black': '#000000'}
        getMeta('theme-color').content = metaColors[document.body.getAttribute('theme')];
    </script>
    <div id="back-to-top"></div>
    <div id="mask"></div><div class="wrapper"><header class="desktop" id="header-desktop">
    <div class="header-wrapper">
        <div class="header-title">
            <a href="/" title=""><span id="desktop-header-typeit" class="typeit"></span></a>
        </div>
        <div class="menu">
            <div class="menu-inner"><a class="menu-item" href="/posts/"> 文章 </a><a class="menu-item" href="/tags/"> 标签 </a><a class="menu-item" href="/series/"> 系列 </a><a class="menu-item" href="/about/"> 关于 </a><span class="menu-item delimiter"></span><a href="#" onclick="return false;" class="menu-item theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a></div>
        </div>
    </div>
</header><header class="mobile" id="header-mobile">
    <div class="header-container">
        <div class="header-wrapper">
            <div class="header-title">
                <a href="/" title=""><span id="mobile-header-typeit" class="typeit"></span></a>
            </div>
            <div class="menu-toggle" id="menu-toggle-mobile">
                <span></span><span></span><span></span>
            </div>
        </div>
        <div class="menu" id="menu-mobile"><a class="menu-item" href="/posts/" title="">文章</a><a class="menu-item" href="/tags/" title="">标签</a><a class="menu-item" href="/series/" title="">系列</a><a class="menu-item" href="/about/" title="">关于</a><a href="#" onclick="return false;" class="menu-item theme-switch" title="切换主题">
                <i class="fas fa-adjust fa-fw"></i>
            </a></div>
    </div>
</header>
<div class="search-dropdown desktop">
    <div id="search-dropdown-desktop"></div>
</div>
<div class="search-dropdown mobile">
    <div id="search-dropdown-mobile"></div>
</div>
<main class="main">
            <div class="container"><div class="toc" id="toc-auto">
        <h2 class="toc-title">目录</h2>
        <div class="toc-content" id="toc-content-auto"><nav id="TableOfContents">
  <ul>
    <li><a href="#解决的问题">解决的问题</a></li>
    <li><a href="#crud">CRUD</a>
      <ul>
        <li><a href="#结构">结构</a></li>
        <li><a href="#寻找">寻找</a></li>
        <li><a href="#插入">插入</a></li>
        <li><a href="#删除to-do">删除(To Do)</a></li>
      </ul>
    </li>
    <li><a href="#优化点to-do">优化点（To Do）</a></li>
  </ul>
</nav></div>
    </div><script>document.getElementsByTagName("main")[0].setAttribute("pageStyle", "normal")</script><script>document.getElementsByTagName("main")[0].setAttribute("autoTOC", "true")</script><article class="page single"><h1 class="single-title animate__animated animate__flipInX">Skiplist</h1><div class="post-meta">
            <div class="post-meta-line">
                <span class="post-author"><i class="author fas fa-user-circle fa-fw"></i><a href="/" title="Author" rel=" author" class="author">作者</a>
                </span>&nbsp;<span class="post-category">收录于 </span>&nbsp;<span class="post-series">系列 <a href="/series/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/"><i class="far fa-list-alt fa-fw"></i>数据结构</a></span></div>
            <div class="post-meta-line"><i class="far fa-calendar-alt fa-fw"></i>&nbsp;<time datetime="2022-03-12">2022-03-12</time>&nbsp;<i class="far fa-edit fa-fw"></i>&nbsp;<time datetime="2022-03-12">2022-03-12</time>&nbsp;<i class="fas fa-pencil-alt fa-fw"></i>&nbsp;约 1918 字&nbsp;
                <i class="far fa-clock fa-fw"></i>&nbsp;预计阅读 4 分钟&nbsp;</div>
        </div><div class="details toc" id="toc-static"  kept="">
                <div class="details-summary toc-title">
                    <span>目录</span>
                    <span><i class="details-icon fas fa-angle-right"></i></span>
                </div>
                <div class="details-content toc-content" id="toc-content-static"><nav id="TableOfContents">
  <ul>
    <li><a href="#解决的问题">解决的问题</a></li>
    <li><a href="#crud">CRUD</a>
      <ul>
        <li><a href="#结构">结构</a></li>
        <li><a href="#寻找">寻找</a></li>
        <li><a href="#插入">插入</a></li>
        <li><a href="#删除to-do">删除(To Do)</a></li>
      </ul>
    </li>
    <li><a href="#优化点to-do">优化点（To Do）</a></li>
  </ul>
</nav></div>
            </div><div class="content" id="content"><h1 id="跳表skiplist" class="headerLink">
    <a href="#%e8%b7%b3%e8%a1%a8skiplist" class="header-mark"></a>跳表(SkipList)</h1><h2 id="解决的问题" class="headerLink">
    <a href="#%e8%a7%a3%e5%86%b3%e7%9a%84%e9%97%ae%e9%a2%98" class="header-mark"></a>解决的问题</h2><p>首先看链表的形式</p>
<p><img
        class="lazyload"
        data-src="https://s2.loli.net/2022/03/12/PzYoHaOXAqWLd3K.png"
        data-srcset="https://s2.loli.net/2022/03/12/PzYoHaOXAqWLd3K.png, https://s2.loli.net/2022/03/12/PzYoHaOXAqWLd3K.png 1.5x, https://s2.loli.net/2022/03/12/PzYoHaOXAqWLd3K.png 2x"
        data-sizes="auto"
        alt="https://s2.loli.net/2022/03/12/PzYoHaOXAqWLd3K.png"
        title="单链表.jpg"></p>
<p>​	由于单链表的形式，当搜索某一个节点时，必须从头开始遍历，在数据量很大的情况，查询的性能就会极其拉跨。由此就衍生再增加一层索引的做法，如下图，当要查找D时，路径只需要A-&gt;C-&gt;D，减少了搜寻的路径(<strong>注意：此处每个节点按大小顺序</strong>)，一般提取索引是每两个节点提取一次。</p>
<p><img
        class="lazyload"
        data-src="https://s2.loli.net/2022/03/12/NeVzxU2wJG57RZY.png"
        data-srcset="https://s2.loli.net/2022/03/12/NeVzxU2wJG57RZY.png, https://s2.loli.net/2022/03/12/NeVzxU2wJG57RZY.png 1.5x, https://s2.loli.net/2022/03/12/NeVzxU2wJG57RZY.png 2x"
        data-sizes="auto"
        alt="https://s2.loli.net/2022/03/12/NeVzxU2wJG57RZY.png"
        title="链表加索引.jpg"></p>
<p>​	但是，引出的新问题是：当第二层索引上的数据同样很多的情况下，此时就会又变成了类似单链表的形式，有一个比较好的解决方法就是：增加更多层的索引，这就是<strong>跳表</strong>，如下图所示，（当然，这是是跳表<strong>大概的形状</strong>，具体形状要看实现时的写法）。</p>
<p><img
        class="lazyload"
        data-src="https://s2.loli.net/2022/03/12/rcFehsuLSAI3vOi.png"
        data-srcset="https://s2.loli.net/2022/03/12/rcFehsuLSAI3vOi.png, https://s2.loli.net/2022/03/12/rcFehsuLSAI3vOi.png 1.5x, https://s2.loli.net/2022/03/12/rcFehsuLSAI3vOi.png 2x"
        data-sizes="auto"
        alt="https://s2.loli.net/2022/03/12/rcFehsuLSAI3vOi.png"
        title="跳表.jpg"></p>
<p>​	比如说，当我们要查找到G这个节点时，以跳表的方式实现的链表，路径为:A-&gt;E-&gt;G，而使用单链表时，路径为：A-&gt;B-&gt;C-&gt;D-&gt;E-&gt;F-&gt;G，几乎减少了一般的查询路径，这种表现在数据量巨大时，会体现出更明显的性能差距对比。现在来回答第一节的问题，跳表解决了什么样的一个问题？<strong>其用多层索引的方式，在节点按大小顺序排列的形况下，减少遍历的节点，带来查询速度的加速。</strong></p>
<h2 id="crud" class="headerLink">
    <a href="#crud" class="header-mark"></a>CRUD</h2><h3 id="结构" class="headerLink">
    <a href="#%e7%bb%93%e6%9e%84" class="header-mark"></a>结构</h3><p>​	跳表是多层的，显然不能单独把每一层分开为多条链表，这样会导致在对跳表操作时增加复杂度。最好的方法是将<strong>同一个节点的多层视为一个Element</strong>，将其回归到链表的结构，从逻辑上看，就有Element1&ndash;&gt;Element2&ndash;&gt;Element3，只是在Element内部设置了多层的指针，分别指向每一层对应的节点。具体形状与结构代码如下图所示：</p>
<p><img
        class="lazyload"
        data-src="https://s2.loli.net/2022/03/12/LIdkfMPz87QKY65.png"
        data-srcset="https://s2.loli.net/2022/03/12/LIdkfMPz87QKY65.png, https://s2.loli.net/2022/03/12/LIdkfMPz87QKY65.png 1.5x, https://s2.loli.net/2022/03/12/LIdkfMPz87QKY65.png 2x"
        data-sizes="auto"
        alt="https://s2.loli.net/2022/03/12/LIdkfMPz87QKY65.png"
        title="Element结构.jpg"></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-go" data-lang="go"><span class="line"><span class="cl"><span class="c1">//Element 结构
</span></span></span><span class="line"><span class="cl"><span class="c1"></span><span class="kd">type</span> <span class="nx">Element</span> <span class="nx">srtuct</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">    <span class="nx">levels</span> <span class="p">[]</span><span class="o">*</span><span class="nx">Element</span>	 <span class="c1">// 每一层对应的下一个节点位置
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>    <span class="nx">entry</span>  <span class="o">*</span><span class="nx">Entry</span>		<span class="c1">// 数据
</span></span></span><span class="line"><span class="cl"><span class="c1"></span><span class="p">}</span>
</span></span><span class="line"><span class="cl"><span class="c1">// 任意的数据
</span></span></span><span class="line"><span class="cl"><span class="c1"></span><span class="kd">type</span> <span class="nx">Entry</span> <span class="nx">sturct</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">    <span class="nx">key</span> <span class="kt">int</span>
</span></span><span class="line"><span class="cl">    <span class="nx">value</span> <span class="kt">int</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span>
</span></span><span class="line"><span class="cl"><span class="c1">// 创建新的跳表节点
</span></span></span><span class="line"><span class="cl"><span class="c1"></span><span class="kd">func</span> <span class="nf">NewElement</span><span class="p">(</span><span class="nx">data</span> <span class="o">*</span><span class="nx">Entry</span><span class="p">,</span> <span class="nx">level</span> <span class="kt">int</span><span class="p">)</span> <span class="o">*</span><span class="nx">Element</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">    <span class="k">return</span> <span class="o">&amp;</span><span class="nx">Element</span><span class="p">{</span>
</span></span><span class="line"><span class="cl">        <span class="nx">levels</span> <span class="p">:</span> <span class="nb">make</span><span class="p">([]</span><span class="o">*</span><span class="nx">Element</span><span class="p">,</span> <span class="nx">level</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
</span></span><span class="line"><span class="cl">        <span class="nx">entry</span>  <span class="p">:</span> <span class="nx">data</span>
</span></span><span class="line"><span class="cl">    <span class="p">}</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span> 
</span></span></code></pre></div><p>有了跳表中的节点，还需要一个跳表结构，为了操作方便，采用类似带头节点的实现方式， 并且记录了当前跳表的存在数据的最高层高，节点数量等一些方便后续操作的元素。</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-go" data-lang="go"><span class="line"><span class="cl"><span class="c1">// SkipList 结构
</span></span></span><span class="line"><span class="cl"><span class="c1"></span><span class="kd">type</span> <span class="nx">SkipList</span> <span class="kd">struct</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">	<span class="nx">header</span> <span class="o">*</span><span class="nx">Element</span>	<span class="c1">// 头节点
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>	<span class="nx">length</span> <span class="kt">int</span>	    <span class="c1">// 节点数量
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>	<span class="nx">maxLevel</span> <span class="kt">int</span>	<span class="c1">// 当前有数据的最高层数
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>	<span class="nx">rand</span> <span class="o">*</span><span class="nx">rand</span><span class="p">.</span><span class="nx">Rand</span> <span class="c1">// 随机数
</span></span></span><span class="line"><span class="cl"><span class="c1"></span><span class="p">}</span>
</span></span></code></pre></div><h3 id="寻找" class="headerLink">
    <a href="#%e5%af%bb%e6%89%be" class="header-mark"></a>寻找</h3><p><img
        class="lazyload"
        data-src="https://s2.loli.net/2022/03/12/PzYoHaOXAqWLd3K.png"
        data-srcset="https://s2.loli.net/2022/03/12/PzYoHaOXAqWLd3K.png, https://s2.loli.net/2022/03/12/PzYoHaOXAqWLd3K.png 1.5x, https://s2.loli.net/2022/03/12/PzYoHaOXAqWLd3K.png 2x"
        data-sizes="auto"
        alt="https://s2.loli.net/2022/03/12/PzYoHaOXAqWLd3K.png"
        title="单链表.jpg"></p>
<p>先看单链表的查询操作：(从头开始，逐个遍历，直到链表尾部)</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-go" data-lang="go"><span class="line"><span class="cl"><span class="k">for</span> <span class="nx">ne</span> <span class="o">:=</span> <span class="nx">header</span><span class="p">;</span> <span class="nx">ne</span> <span class="o">!=</span> <span class="kc">nil</span><span class="p">;</span> <span class="nx">ne</span> <span class="p">=</span> <span class="nx">ne</span><span class="p">.</span><span class="nx">next</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">    <span class="k">if</span> <span class="nx">ne</span><span class="p">.</span><span class="nx">key</span> <span class="o">&lt;=</span> <span class="nx">want</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">        <span class="k">if</span> <span class="nx">ne</span><span class="p">.</span><span class="nx">key</span> <span class="o">==</span> <span class="nx">want</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">			<span class="k">return</span> <span class="nx">ne</span><span class="p">.</span><span class="nx">value</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="k">continue</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span>
</span></span><span class="line"><span class="cl">    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">		<span class="k">return</span> <span class="kc">nil</span>
</span></span><span class="line"><span class="cl">    <span class="p">}</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span> 
</span></span><span class="line"><span class="cl"><span class="k">return</span> <span class="kc">nil</span>
</span></span></code></pre></div><p><img
        class="lazyload"
        data-src="https://s2.loli.net/2022/03/12/DHtEqwOgbaTsAFd.jpg"
        data-srcset="https://s2.loli.net/2022/03/12/DHtEqwOgbaTsAFd.jpg, https://s2.loli.net/2022/03/12/DHtEqwOgbaTsAFd.jpg 1.5x, https://s2.loli.net/2022/03/12/DHtEqwOgbaTsAFd.jpg 2x"
        data-sizes="auto"
        alt="https://s2.loli.net/2022/03/12/DHtEqwOgbaTsAFd.jpg"
        title="跳表查询.jpg"></p>
<p>由于跳表是从单链表衍生出来的，所以查询方法也是类似，只不过从单链表的节点遍历，变成多层的element遍历。</p>
<p>设定的跳表的节点是以<strong>大-&gt;小</strong>（也可以使用其他规则）的顺序来存放，因此在查询时，有以下的规律：</p>
<ul>
<li>want = 当前节点，查询成功</li>
<li>want &lt; 当前节点，查询下一个节点</li>
<li>want &gt; 当前节点，移到下一层继续查询</li>
<li>当level == 0 &amp;&amp; want &gt; 当前节点，即该want不存在</li>
</ul>
<p>以上图为例，查询节点D，有以下的步骤：(want = D)，图中黑色箭头就是查询的路径</p>
<ol>
<li>want &lt; A  &ndash;&gt; want &gt; I，移至下一层</li>
<li>want &gt; E， 移至下一层</li>
<li>want &lt; C &ndash;&gt; want &gt; E， 移至下一层</li>
<li>want == D， 查询成功</li>
</ol>
<p>由此可以抽象出查询的逻辑</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-go" data-lang="go"><span class="line"><span class="cl"><span class="kd">func</span> <span class="p">(</span><span class="nx">list</span> <span class="o">*</span><span class="nx">SkipList</span><span class="p">)</span> <span class="nf">search</span><span class="p">(</span><span class="nx">key</span> <span class="kt">int</span><span class="p">)</span> <span class="o">*</span><span class="nx">Entry</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">    
</span></span><span class="line"><span class="cl">    <span class="k">if</span> <span class="nx">list</span><span class="p">.</span><span class="nx">length</span> <span class="o">==</span> <span class="mi">0</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">        <span class="k">return</span> <span class="kc">nil</span>
</span></span><span class="line"><span class="cl">    <span class="p">}</span>
</span></span><span class="line"><span class="cl">    
</span></span><span class="line"><span class="cl">	<span class="nx">prev</span> <span class="o">:=</span> <span class="nx">list</span><span class="p">.</span><span class="nx">header</span>   <span class="c1">//用于记录前面查询到哪一个节点,用于记录下一层从哪个节点开始
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>	<span class="nx">max</span> <span class="o">:=</span> <span class="nx">list</span><span class="p">.</span><span class="nx">maxLevel</span>  <span class="c1">//此跳表存在真正数据的最高层
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>	
</span></span><span class="line"><span class="cl">	<span class="k">for</span> <span class="nx">i</span> <span class="o">:=</span> <span class="nx">max</span><span class="p">;</span> <span class="nx">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="nx">i</span><span class="o">--</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">		<span class="k">for</span> <span class="nx">ne</span> <span class="o">:=</span> <span class="nx">prev</span><span class="p">.</span><span class="nx">level</span><span class="p">[</span><span class="nx">i</span><span class="p">];</span> <span class="nx">ne</span> <span class="o">!=</span> <span class="kc">nil</span><span class="p">;</span> <span class="nx">ne</span> <span class="p">=</span> <span class="nx">prev</span><span class="p">.</span><span class="nx">level</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="k">if</span> <span class="nx">comm</span> <span class="o">:=</span> <span class="nx">list</span><span class="p">.</span><span class="nf">compare</span><span class="p">(</span><span class="nx">key</span><span class="p">,</span> <span class="nx">ne</span><span class="p">.</span><span class="nx">entry</span><span class="p">.</span><span class="nx">key</span><span class="p">);</span> <span class="nx">comm</span> <span class="o">&lt;=</span> <span class="mi">0</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">                <span class="k">if</span> <span class="nx">comm</span> <span class="o">==</span> <span class="mi">0</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">                    <span class="k">return</span> <span class="nx">ne</span><span class="p">.</span><span class="nx">entry</span>
</span></span><span class="line"><span class="cl">                <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">                    <span class="nx">prev</span> <span class="p">=</span> <span class="nx">ne</span>
</span></span><span class="line"><span class="cl">                <span class="p">}</span>
</span></span><span class="line"><span class="cl">            <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">                <span class="k">break</span> <span class="c1">//到下一层寻找
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>            <span class="p">}</span>
</span></span><span class="line"><span class="cl">		<span class="p">}</span>
</span></span><span class="line"><span class="cl">	<span class="p">}</span>
</span></span><span class="line"><span class="cl">	<span class="k">return</span> <span class="kc">nil</span><span class="c1">// key not exist
</span></span></span></code></pre></div><h3 id="插入" class="headerLink">
    <a href="#%e6%8f%92%e5%85%a5" class="header-mark"></a>插入</h3><p>先看单链表的插入方式：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-go" data-lang="go"><span class="line"><span class="cl"><span class="c1">//找到插入的位置，prev后面
</span></span></span><span class="line"><span class="cl"><span class="c1">//新的节点  node
</span></span></span><span class="line"><span class="cl"><span class="c1"></span><span class="nx">tmep</span> <span class="o">:=</span> <span class="nx">prev</span><span class="p">.</span><span class="nx">next</span>
</span></span><span class="line"><span class="cl"><span class="nx">prev</span><span class="p">.</span><span class="nx">next</span> <span class="p">=</span> <span class="nx">node</span>
</span></span><span class="line"><span class="cl"><span class="nx">node</span><span class="p">.</span><span class="nx">next</span> <span class="p">=</span> <span class="nx">temp</span>
</span></span></code></pre></div><p>而，在跳表里，也存在类似的操作，只是需要将每一层都要插入，具体如下：</p>
<ol>
<li>创建新节点</li>
<li>查找每一层插入的位置记录在 prevs<i class="far fa-square fa-fw"></i> 中</li>
<li>在每一层进行插入索引</li>
</ol>
<p>此处还有一个关注点，即插入节点时索引是否更新的问题，就出现了两种选择</p>
<ol>
<li>重构索引</li>
<li>动态更新</li>
</ol>
<p>此处采用的是<strong>动态更新</strong>，此时要考虑的是，新进来的节点的索引最高层应该到哪？</p>
<p>一般每隔两个节点就提升一层，因此可以总结出，一个节点到第1层的概率为 1/2， 2层为 1/4， 3层1/8。。。因此可以设计出：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-go" data-lang="go"><span class="line"><span class="cl"><span class="c1">// MAX 是既定设置的 SkipList能索引的最高的高度
</span></span></span><span class="line"><span class="cl"><span class="c1"></span><span class="nf">fucn</span> <span class="p">(</span><span class="nx">list</span> <span class="o">*</span><span class="nx">SkipList</span><span class="p">)</span> <span class="nf">RandLevel</span><span class="p">()</span> <span class="kt">int</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">	<span class="nx">level</span> <span class="o">:=</span> <span class="mi">1</span>
</span></span><span class="line"><span class="cl">	<span class="k">for</span> <span class="p">;</span> <span class="nx">level</span> <span class="p">&lt;</span> <span class="nx">MAX</span><span class="p">;</span> <span class="nx">level</span><span class="o">++</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">		<span class="k">if</span> <span class="nx">rand</span><span class="p">.</span><span class="nb">int</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span> <span class="o">==</span> <span class="mi">1</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">			<span class="k">return</span> <span class="nx">level</span>
</span></span><span class="line"><span class="cl">		<span class="p">}</span>
</span></span><span class="line"><span class="cl">	<span class="p">}</span>
</span></span><span class="line"><span class="cl">	<span class="k">return</span> <span class="nx">MAX</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span>
</span></span></code></pre></div><p>因此，将添加新节点操作抽象成代码：</p>
<p>此处判断 randlevel 和 list.maxLevel 大小的原因是：为了每次搜索都从<strong>有数据的最高层</strong>开始查询，而不是从既定的MAX层开始，减少查找无用的次数。</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-go" data-lang="go"><span class="line"><span class="cl"><span class="kd">func</span> <span class="p">(</span><span class="nx">list</span> <span class="o">*</span><span class="nx">SkipList</span><span class="p">)</span> <span class="nf">add</span><span class="p">(</span><span class="nx">data</span> <span class="o">*</span><span class="nx">Entry</span><span class="p">)</span> <span class="kt">error</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">	<span class="c1">//创建新节点
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>	<span class="nx">randlevel</span> <span class="o">:=</span> <span class="nx">list</span><span class="p">.</span><span class="nf">RandLevel</span><span class="p">()</span>
</span></span><span class="line"><span class="cl">	<span class="k">if</span> <span class="nx">randlevel</span> <span class="p">&gt;</span> <span class="nx">list</span><span class="p">.</span><span class="nx">maxLevel</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">		<span class="nx">list</span><span class="p">.</span><span class="nx">maxLevel</span> <span class="p">=</span> <span class="nx">randlevel</span>
</span></span><span class="line"><span class="cl">	<span class="p">}</span>
</span></span><span class="line"><span class="cl">	<span class="nx">element</span> <span class="o">:=</span> <span class="nf">NewElement</span><span class="p">(</span><span class="nx">data</span><span class="p">,</span> <span class="nx">randlevel</span><span class="p">)</span>
</span></span><span class="line"><span class="cl">	<span class="c1">//查找插入的位置
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>	<span class="nx">prev</span> <span class="o">:=</span> <span class="nx">list</span><span class="p">.</span><span class="nx">header</span>
</span></span><span class="line"><span class="cl">	<span class="nx">prevs</span> <span class="o">:=</span> <span class="nb">make</span><span class="p">([]</span><span class="o">*</span><span class="nx">Element</span><span class="p">,</span> <span class="nx">list</span><span class="p">.</span><span class="nx">maxLevel</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> 
</span></span><span class="line"><span class="cl">	<span class="k">for</span> <span class="nx">i</span> <span class="o">:=</span> <span class="nx">list</span><span class="p">.</span><span class="nx">maxLevel</span><span class="p">;</span> <span class="nx">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="nx">i</span><span class="o">--</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">		
</span></span><span class="line"><span class="cl">		<span class="k">for</span> <span class="nx">ne</span> <span class="o">:=</span> <span class="nx">prev</span><span class="p">.</span><span class="nx">level</span><span class="p">[</span><span class="nx">i</span><span class="p">];</span> <span class="nx">ne</span> <span class="o">!=</span> <span class="kc">nil</span><span class="p">;</span> <span class="nx">ne</span> <span class="p">=</span> <span class="nx">prev</span><span class="p">.</span><span class="nx">level</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">			<span class="k">if</span> <span class="nx">com</span> <span class="o">:=</span> <span class="nx">list</span><span class="p">.</span><span class="nf">compare</span><span class="p">(</span><span class="nx">data</span><span class="p">.</span><span class="nx">key</span><span class="p">,</span> <span class="nx">ne</span><span class="p">.</span><span class="nx">entry</span><span class="p">.</span><span class="nx">key</span><span class="p">);</span> <span class="nx">com</span> <span class="o">&lt;=</span> <span class="mi">0</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">				<span class="k">if</span> <span class="nx">comm</span> <span class="o">==</span> <span class="mi">0</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">					<span class="c1">//相等，直接更新
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>					<span class="nx">ne</span><span class="p">.</span><span class="nx">entry</span> <span class="p">=</span> <span class="nx">data</span>
</span></span><span class="line"><span class="cl">					<span class="k">return</span> <span class="kc">nil</span>
</span></span><span class="line"><span class="cl">				<span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">					<span class="nx">prev</span> <span class="p">=</span> <span class="nx">ne</span>
</span></span><span class="line"><span class="cl">				<span class="p">}</span>
</span></span><span class="line"><span class="cl">			<span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">				<span class="k">break</span>
</span></span><span class="line"><span class="cl">			<span class="p">}</span>
</span></span><span class="line"><span class="cl">		<span class="p">}</span>
</span></span><span class="line"><span class="cl">		<span class="nx">prevs</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span> <span class="p">=</span> <span class="nx">prev</span>
</span></span><span class="line"><span class="cl">	<span class="p">}</span>
</span></span><span class="line"><span class="cl">	<span class="c1">//插入
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>	<span class="k">for</span> <span class="nx">i</span> <span class="o">:=</span> <span class="nx">randlevel</span><span class="p">;</span> <span class="nx">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="nx">i</span><span class="o">--</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">		<span class="nx">ne</span> <span class="o">:=</span> <span class="nx">prevs</span><span class="p">[</span><span class="nx">i</span><span class="p">].</span><span class="nx">level</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span>
</span></span><span class="line"><span class="cl">		<span class="nx">element</span><span class="p">.</span><span class="nx">level</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span> <span class="p">=</span> <span class="nx">ne</span>
</span></span><span class="line"><span class="cl">		<span class="nx">prevs</span><span class="p">[</span><span class="nx">i</span><span class="p">].</span><span class="nx">level</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span> <span class="p">=</span> <span class="nx">element</span>
</span></span><span class="line"><span class="cl">	<span class="p">}</span>
</span></span><span class="line"><span class="cl">	<span class="nx">list</span><span class="p">.</span><span class="nx">length</span><span class="o">++</span> <span class="c1">// 插入新节点，跳表长度 + 1
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>	<span class="k">return</span> <span class="kc">nil</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span>
</span></span></code></pre></div><h3 id="删除to-do" class="headerLink">
    <a href="#%e5%88%a0%e9%99%a4to-do" class="header-mark"></a>删除(To Do)</h3><h2 id="优化点to-do" class="headerLink">
    <a href="#%e4%bc%98%e5%8c%96%e7%82%b9to-do" class="header-mark"></a>优化点（To Do）</h2><ol>
<li>优化比较的逻辑</li>
<li>randLevel函数的优化，将索引的高度提升到更合适的位置</li>
<li>&hellip;</li>
</ol>
</div>

        <div class="post-footer" id="post-footer">
    <div class="post-info">
        <div class="post-info-line">
            <div class="post-info-mod">
                <span>更新于 2022-03-12</span>
            </div>
            <div class="post-info-license"></div>
        </div>
        <div class="post-info-line">
            <div class="post-info-md"></div>
            <div class="post-info-share">
                <span><a href="#" onclick="return false;" title="分享到 Twitter" data-sharer="twitter" data-url="http://gzhcoming.gitee.io/posts/%E8%B7%B3%E8%A1%A8skiplist/" data-title="Skiplist" data-hashtags="data struct"><i class="fab fa-twitter fa-fw"></i></a><a href="#" onclick="return false;" title="分享到 Facebook" data-sharer="facebook" data-url="http://gzhcoming.gitee.io/posts/%E8%B7%B3%E8%A1%A8skiplist/" data-hashtag="data struct"><i class="fab fa-facebook-square fa-fw"></i></a><a href="#" onclick="return false;" title="分享到 Hacker News" data-sharer="hackernews" data-url="http://gzhcoming.gitee.io/posts/%E8%B7%B3%E8%A1%A8skiplist/" data-title="Skiplist"><i class="fab fa-hacker-news fa-fw"></i></a><a href="#" onclick="return false;" title="分享到 Line" data-sharer="line" data-url="http://gzhcoming.gitee.io/posts/%E8%B7%B3%E8%A1%A8skiplist/" data-title="Skiplist"><i data-svg-src="/lib/simple-icons/icons/line.min.svg"></i></a><a href="#" onclick="return false;" title="分享到 微博" data-sharer="weibo" data-url="http://gzhcoming.gitee.io/posts/%E8%B7%B3%E8%A1%A8skiplist/" data-title="Skiplist"><i class="fab fa-weibo fa-fw"></i></a><a href="#" onclick="return false;" title="分享到 Telegram" data-sharer="telegram" data-url="http://gzhcoming.gitee.io/posts/%E8%B7%B3%E8%A1%A8skiplist/" data-title="Skiplist" data-web><i class="fab fa-telegram-plane fa-fw"></i></a></span>
            </div>
        </div>
    </div>

    <div class="post-info-more">
        <section class="post-tags"><i class="fas fa-tags fa-fw"></i>&nbsp;<a href="/tags/data-struct/">data struct</a></section>
        <section>
            <span><a href="javascript:void(0);" onclick="window.history.back();">返回</a></span>&nbsp;|&nbsp;<span><a href="/">主页</a></span>
        </section>
    </div>

    <div class="post-nav"><a href="/posts/081-utilities/" class="prev" rel="prev" title="081 Utilities"><i class="fas fa-angle-left fa-fw"></i>081 Utilities</a>
            <a href="/posts/git/" class="next" rel="next" title="Git">Git<i class="fas fa-angle-right fa-fw"></i></a></div>
</div>
</article></div>
        </main><footer class="footer">
        <div class="footer-container"><div class="footer-line">
                    由 <a href="https://gohugo.io/" target="_blank" rel="noopener noreffer" title="Hugo 0.96.0">Hugo</a> 强力驱动&nbsp;|&nbsp;主题 - <a href="https://github.com/HEIGE-PCloud/DoIt" target="_blank" rel="noopener noreffer" title="DoIt 0.2.13"><i class="far fa-edit fa-fw"></i> DoIt</a>
                </div><div class="footer-line"><i class="far fa-copyright fa-fw"></i><span itemprop="copyrightYear">2022</span><span class="author" itemprop="copyrightHolder">&nbsp;<a href="/" target="_blank" rel="noopener noreferrer"></a></span></div>
            <div class="footer-line"></div>
            <div class="footer-line">
            </div>
        </div></footer></div>

    <div id="fixed-buttons"><a href="#back-to-top" id="back-to-top-button" class="fixed-button" title="回到顶部">
            <i class="fas fa-arrow-up fa-fw"></i>
        </a><a href="#" id="view-comments" class="fixed-button" title="查看评论">
            <i class="fas fa-comment fa-fw"></i>
        </a>
    </div><div class="assets"><script type="text/javascript" src="/lib/lazysizes/lazysizes.min.js"></script><script type="text/javascript" src="/lib/topbar/topbar.min.js"></script><script type="text/javascript" src="/lib/pjax/pjax.min.js"></script><script type="text/javascript" src="/js/theme.min.js"></script></div>

<div class="pjax-assets"><script type="text/javascript">window.config={"code":{"copyTitle":"复制到剪贴板","maxShownLines":10},"comment":{},"data":{"desktop-header-typeit":"Gzh's blog","mobile-header-typeit":"Gzh's blog"},"sharerjs":true,"typeit":{"cursorChar":null,"cursorSpeed":null,"data":{"desktop-header-typeit":["desktop-header-typeit"],"mobile-header-typeit":["mobile-header-typeit"]},"duration":null,"speed":null}};</script><script type="text/javascript" src="/lib/clipboard/clipboard.min.js"></script><script type="text/javascript" src="/lib/sharer/sharer.min.js"></script><script type="text/javascript" src="/lib/typeit/typeit.min.js"></script></div>
</body>

</html>